//单词规律
/*给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。*/
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> hash;
        unordered_map<string, char> _hash;

        int left = 0, right = 0;
        for (int i = 0; i < pattern.size(); i++) {
            if (right > s.size())
                return false;
            while (s[right] != ' ' && right < s.size()) {
                right++;
            }
            string temp(s.begin() + left, s.begin() + right);
            right++;
            left = right;
            if (hash.count(pattern[i])) {
                if (hash[pattern[i]] != temp)
                    return false;
            } else {
                hash[pattern[i]] = temp;
            }
            if (_hash.count(temp)) {
                if (_hash[temp] != pattern[i])
                    return false;
            } else {
                _hash[temp] = pattern[i];
            }
        }
        if (right >= s.size())
            return true;
        return false;
    }
};


//生命游戏
/*根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

给定当前 board 的状态，更新 board 到下一个状态。

注意 你不需要返回任何东西。*/
class Solution {
    int dx[8] = {1, -1, -1, 1, 1, -1, 0, 0};
    int dy[8] = {1, -1, 1, -1, 0, 0, 1, -1};

public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<pair<int, int>> hash;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0;
                // 统计周围细胞个数
                for (int k = 0; k < 8; k++) {
                    if (i + dx[k] < m && j + dy[k] < n && i + dx[k] >= 0 &&
                        j + dy[k] >= 0 && board[i + dx[k]][j + dy[k]])
                        count++;
                }
                if (board[i][j]) {
                    if (!(count == 2 || count == 3))
                    // board[i][j] = 0;
                    {
                        hash.emplace_back(i, j);
                    }
                } else {
                    if (count == 3)
                        // board[i][j] = 1;
                        hash.emplace_back(i, j);
                }
                // cout << count << ' ';
            }

            // cout << endl;
        }
        for (auto& P : hash) {
            int f = P.first;
            int s = P.second;
            if (board[f][s])
                board[f][s] = 0;
            else
                board[f][s] = 1;
        }
    }
};